#ifndef __RadixSort_H__
#define __RadixSort_H__

#include <neinit.h>

namespace ne
{
    enum SortMode
    {
        SM_LESS,
        SM_GREATER,
        SM_DISTANCE,
        SM_DIRECTION
    };

	// TODO: RadixSort32 we can radix sort a maximum of a 32bit value Little to Big
    template <typename TContainer, typename TContainerValueType, typename TCompValueType>
	class RadixSort32
	{
        public:
            typedef typename TContainer::iterator ContainerIter;

            struct SortEntry
            {
                TCompValueType key;
                ContainerIter iter;
                SortEntry() {}
                SortEntry(TCompValueType k, ContainerIter it) : key(k), iter(it) {}
            };

            typedef std::vector<SortEntry> SortVector;

        public:
            RadixSort32() {}
            virtual ~RadixSort32() {}

            /** Main sort function
            @param container A container of the type you declared when declaring
            @param func A functor which returns the value for comparison when given
                a container value
            */
            template <typename TFunction>
            void sort(TContainer& container, TFunction func)
            {
                if (container.empty())
                    return;

                // Set up the sort areas
                mSortSize = container.size();
                mSortArea1.resize(container.size());
                mSortArea2.resize(container.size());

                // Copy data now (we need constant iterators for sorting)
                mTmpContainer = container;
                mNumPasses = sizeof(TCompValueType);

                // Counter pass
                // Initialise the counts
                int p = 0;
                for (p=0; p<mNumPasses; ++p)
                {
                    memset(mCounters[p], 0, sizeof(int) * 256);
                }

                // Perform alpha pass to count
                ContainerIter it = mTmpContainer.begin();
                ContainerIter iend = mTmpContainer.end();
                TCompValueType prevValue = func.operator()(*it); 
                bool needsSorting = false;
                for (int u=0; it!=iend; ++u, ++it)
                {
                    // Get sort value
                    TCompValueType val = func.operator()(*it);
                    // Cheap check to see if needs sorting (temporal coherence)
                    if (!needsSorting && val < prevValue)
                    {
                        needsSorting = true;
                    }

                    // Create a sort entry
                    mSortArea1[u].key = val;
                    mSortArea1[u].iter = it;

                    // Increase counters
                    for (p=0; p<mNumPasses; ++p)
                    {
                        byte byteVal = _getByte(p, val);
                        ++mCounters[p][byteVal];
                    }

                    prevValue = val;
                }

                // Early exit if already sorted
                if (!needsSorting)
                {
                    return;
                }

                // Sort passes
                mSrc = &mSortArea1;
                mDest = &mSortArea2;

                for (p=0; p<mNumPasses-1; ++p)
                {
                    _sortPass(p);
                    // Swep src and dst
                    SortVector *tmp = mSrc;
                    mSrc = mDest;
                    mDest = tmp;
                }
                // Final pass may differ, make polymorphic
                _finalPass(p, prevValue);

                // Copy everything back
                it = container.begin();
                iend = container.end();
                for (p=0; it!=iend; ++p, ++it)
                {
                    *it = *((*mDest)[p].iter);
                }
            }

        protected:
            void _sortPass(int byteIndex)
            {
                // Calculate offsets
                // Basically this just leaves gaps for duplicate entries to fill
                mOffsets[0] = 0;
                for (int i=1; i<256; ++i)
                {
                    mOffsets[i] = mOffsets[i - 1] + mCounters[byteIndex][i - 1];
                }

                // Sort pass
                for (int i=0; i<mSortSize; ++i)
                {
                    byte byteVal = _getByte(byteIndex, (*mSrc)[i].key);
                    (*mDest)[mOffsets[byteVal]++] = (*mSrc)[i];
                }

            }

            template <typename T>
            void _finalPass(int byteIndex, T val)
            {
                // Default is to do normal pass
                _sortPass(byteIndex);
            }

            // Special case signed int
            void _finalPass(int byteIndex, int val)
            {
                int numNeg = 0;
                // All negative values are in entries 128+ in most significant byte
                for (int i=128; i<256; ++i)
                {
                    numNeg += mCounters[byteIndex][i];
                }
                // Calculate offsets - positive ones start at the number of negatives
                // do positive numbers
                mOffsets[0] = numNeg;
                for (int i=1; i<128; ++i)
                {
                    mOffsets[i] = mOffsets[i - 1] + mCounters[byteIndex][i - 1];
                }
                // Do negative numbers (must start at zero)
                // No need to invert ordering, already correct (-1 is highest number)
                mOffsets[128] = 0;
                for (int i=129; i<256; ++i)
                {
                    mOffsets[i] = mOffsets[i - 1] + mCounters[byteIndex][i - 1];
                }

                // Sort pass
                for (int i=0; i<mSortSize; ++i)
                {
                    byte byteVal = _getByte(byteIndex, (*mSrc)[i].key);
                    (*mDest)[mOffsets[byteVal]++] = (*mSrc)[i];
                }
            }

            // special case float
            void _finalPass(int byteIndex, float val)
            {
                // Floats need to be special cased since negative numbers will come
                // after positives (high bit = sign) and will be in reverse order
                // (no ones-complement of the +ve value)
                int numNeg = 0;
                // All negative values are in entries 128+ in most significant byte
                for (int i=128; i<256; ++i)
                {
                    numNeg += mCounters[byteIndex][i];
                }
                // Calculate offsets - positive ones start at the number of negatives
                // do positive numbers normally
                mOffsets[0] = numNeg;
                for (int i=1; i<128; ++i)
                {
                    mOffsets[i] = mOffsets[i - 1] + mCounters[byteIndex][i - 1];
                }
                // Do negative numbers (must start at zero)
                // Also need to invert ordering
                // In order to preserve the stability of the sort (essential since
                // we rely on previous bytes already being sorted) we have to count
                // backwards in our offsets from 
                mOffsets[255] = mCounters[byteIndex][255];
                for (int i=254; i>127; --i)
                {
                    mOffsets[i] = mOffsets[i + 1] + mCounters[byteIndex][i];
                }

                // Sort pass
                for (int i=0; i<mSortSize; ++i)
                {
                    byte byteVal = _getByte(byteIndex, (*mSrc)[i].key);
                    if (byteVal > 127)
                    {
                        // -ve; pre-decrement since offsets set to count
                        (*mDest)[--mOffsets[byteVal]] = (*mSrc)[i];
                    }
                    else
                    {
                        // +ve
                        (*mDest)[mOffsets[byteVal]++] = (*mSrc)[i];
                    }
                }
            }

            inline byte _getByte(int byteIndex, TCompValueType val)
            {
#if NE_ENDIAN == NE_ENDIAN_LITTLE
                return ((byte*)(&val))[byteIndex];
#else
                return ((byte*)(&val))[mNumPasses - byteIndex - 1];
#endif
            }

        private:
            RadixSort32(const RadixSort32 &);

            RadixSort32& operator = (const RadixSort32 &);

        protected:
            /// Alpha-pass counters of values (histogram)
            /// 4 of them so we can radix sort a maximum of a 32bit value
            int mCounters[4][256];
            /// Beta-pass offsets 
            int mOffsets[256];
            /// Sort area size
            int mSortSize;
            /// Number of passes for this type
            int mNumPasses;

            SortVector mSortArea1;
            SortVector mSortArea2;
            SortVector* mSrc;
            SortVector* mDest;
            TContainer mTmpContainer; // Initial copy
	};
}

#endif
